Logic arrays are used in digital data processing systems to perform logic calculations or transformations; that is, to process data by furnishing data signal outputs which are determined by data signal inputs in accordance with prescribed logic transformation rules. For this purpose, programmed logic arrays (PLAs) provide an easily designed and well structured alternative to random (individually distributed) combinatorial (or "combinational") logic devices. The advantages of a PLA stem from its compact integrated circuit layout and its ease of systematic design once the desired logic transformation rule or function (output vs. input) or "characteristic table" is prescribed. Also, because of a PLA's patterned array structure, redefinition of its logical transformation function can be as easily accomplished as modification of a conventional ROM (Read Only Memory) array, i.e., by modification of the pattern of array crosspoints at which cross-connection elements are present vs. absent.
Internally, a conventional PLA comprises two logic array portions known as the AND plane (also known as the DECODER array portion) and the OR plane (also known as the ROM array portion). The AND and OR planes are electrically connected together by paths or lines known as interconnecting (or intermediate) wordlines, say n in number. During operation, a sequence of PLA binary input data signal combinations is entered into the AND plane on a plurality of input lines, say N in number, in order to furnish a sequence of binary input combinations or input words--for example, each word formed by a binary bit string, such as (1,0,1 . . . 0,1,0), of binary digital bits, N in number--a sequence of PLA binary output data signals or output words emanates in response thereto from the OR plane on a plurality of output lines, say P in number. When the PLA is adapted for use as a finite state machine, one or more of the binary output signals from the OR plane can be fed back as input bits to the AND plane. Both AND and OR planes, in certain specific embodiments, comprise orthogonal row and column lines mutually intersecting at crosspoints; and at each of the crosspoints is situated or is not situated a crosspoint connecting link such as a transistor, depending upon the desired logic transformation function of the PLA.
The binary signal on a line carrying data in the PLA can be either logic HIGH, representing the binary digital bit ONE ("1"), or else logic LOW, representing the binary digital bit ZERO ("0"). Ordinarily, a given intermediate wordline (between AND and OR planes) will be logic HIGH (binary ONE or 1) if and only if the input word introduced on the input lines of the AND plane is a correspondingly given word. In a specific example, for purpose of illustration, the given intermediate wordline will be logic HIGH if and only if the input word is the bit string characterized by the first bit (I.sub.1) being logic HIGH (I.sub.1 =1), and the second bit (I.sub.2) being logic LOW (I.sub.2 =0), and the third bit (I.sub.3) being logic HIGH (I.sub.3 =1), and . . . and the last bit (I.sub.N) being logic LOW; that is, if and only if I.sub.1 =1 and I.sub.2 =0 and I.sub.3 =1 and . . . and I.sub.N =0 (where N is the number of bits in the input word and hence I.sub.N is the last (N'th) bit). On the other hand, the output signal on a given output line (a given output bit) emanating from the OR plane is logic LOW if and only if any one or more of a given group of intermediate wordlines is logic HIGH, that is, for a specific example, if and only if the first wordline (W.sub.1) is logic HIGH, or the third wordline (W.sub.3) is logic HIGH, or the sixth wordline (W.sub.6) is logic HIGH; that is, the given output bit is ZERO when and only when W=1 or W.sub.3 =1 or W.sub.6 =1. In this way, the PLA supplies output words which are (Boolean) functions of the input words.
In ordinary operation with a PLA, it is desired that the PLA should handle many input words in sequence, one input word after another; that is, that the PLA should perform its prescribed transformation on many words of input data, one input word after another, and should deliver its corresponding output words in sequence, one output word after another. Accordingly, the PLA is supplied with data shifting means (shift registers) for repetitively temporarily storing and shifting (transferring) data into, through, and out of, the PLA--all in accordance with a suitable time sequence, so as to avoid confusion of one word or set of data (say, old data) with another (say, new data) in the PLA. Moreover, the PLA must be able to receive each new input word and to deliver each new output word at appropriate respective moments of time or during appropriate time intervals, according to the system requirements of the rest of the data processing system in which the PLA operates. Such system requirements typically are "synchronous": that is, PLA receives data from and delivers data to the rest of the system in response to (periodic) clock control timing, typically in the form of a sequence of clock pulses. In such a case, the PLA can receive input data only during a first predetermined portion or phase of each cycle (period) of the clock control, and the PLA can deliver output data only during a second predetermined (in general, different) portion or phase of each such cycle of the clock. For example, if the clock has two phases (.phi..sub.1, .phi..sub.2) per cycle, then the PLA typically receives data during one of the phases (.phi..sub.1) and delivers data during the other of the phases (.phi..sub.2) of each cycle. If the clock has a cycle time or period equal to T, then the PLA can thus receive and deliver 1/T words per unit time. Accordingly, the rate at which the PLA processes (receives and delivers) data is inversely proportional to the period T of the control clock and is directly proportional to the clock frequency f=1/T.
The data shifting means required in a PLA ordinarily takes the form of a pair of clocked parallel shift registers for temporarily storing periodically shifting data. Each register typically takes the form of a group of flip-flop devices (each device being a pair of cross-coupled inverters, the output of one being the input of the other) mutually arranged in parallel, that is, so that each entire binary word being processed by the PLA can be transferred (entered) into, temporarily stored in, and transferred out of the register--all in response to a single clock cycle of the control timing supplied to the registers. The pair of registers is ordinarily connected and supplied with control timing so as to operate in a "master-slave" relationship, that is, one of the registers serving as the "master" register and the other as its "slave." By definition, the master receives data from an external source (such as another register) and its slave receives data from its master, all in response to control timing arranged so that when one of the registers (master or slave) can receive new data, the other cannot.
Thus, for example, during a first phase of a cycle of the clock used to control the timing of both master and slave, data can enter into the master register but not into its slave, and during a second phase of the control cycle, data is shifted (transferred) from the master into its slave register but then no data can enter into the master.
In prior art, a single pair of registers is thus used in master-slave relationship to control the flow of data through a PLA, and thus the PLA operates with single-level control timing whereby data is transferred through and is processed by the PLA within a single clock cycle. Thus in prior art input data enters into, is transformed by, and emanates from the PLA as (logically transformed) output data all during a single cycle (or "clock period") of the control timing of the registers.
Single-level control timing is exemplified in the prior art by placing a master register in the wordlines, between the AND and OR planes of a PLA, and a slave register in the output lines of the OR plane of the PLA as described in greater detail in a paper by E. Hebenstreit et al entitled "High-Speed Programmable Logic Arrays in ESFI SOS Technology," published in IEEE Journal of Solid State Circuits, Vol. SC-11, pp. 370-374 (1976). Alternatively, a master register can be placed on the input lines of the AND plane and a slave register on the output lines of the OR plane.
There is an upper limit on the above-mentioned clock frequency f=1/T usable by the PLA, and hence upon the rate at which the PLA can process data. This upper limit stems from the inherent propagation delay times of the circuit components of the PLA (AND plane, OR plane, and registers), that is, the minimum time required for data to be transferred from one (input) end of a component to the other (output) end thereof regardless of how fast the clock frequency may be. A typical cause of such delay in a circuit component is the RC time constant of interconnecting metallization (wiring) of the AND plane.
Because of the relatively large physical sizes of the AND and OR planes along the directions of data propagation, the propagation delay through either of these planes is ordinarily much larger (by a factor of about ten or more) than the propagation delay through a register. For proper operation, however, to avoid undesirable confusion of old and new data, the clock cycle time or period used in single-level PLA control timing should be greater than the sum of the propagation delays of the AND and OR planes plus the sum of the propagation delays of the registers. Accordingly, the speed of the clock that can be used to control the timing of the registers in prior art single-level control timing is limited (ordinarily) to approximately the sum of the propagation delays of the AND and OR planes (that is, neglecting the relatively small delays of the registers themselves). Hence, the maximum speed of operation of the PLA is likewise limited by approximately the sum of these propagation delays; that is, the minimum time interval between successive words that can be processed and delivered by the PLA is limited to approximately this sum of propagation delays. Moreover, the maximum speed at which the PLA can operate is often the limiting factor on the overall speed of operation of the entire data processing system in which the PLA operates. It would therefore be desirable to have a means for increasing the maximum possible speed at which a given PLA can operate. On the other hand, in other systems it is sometimes desirable to use a more powerful PLA, i.e., of larger logic transformation capacity--that is, capable of handling longer (more bits) input and output words and more wordlines--but such larger PLA size would entail an undesirable decrease in maximum possible operating speed. If the above-mentioned desirable means for increasing the maximum possible PLA operating speed would be available, larger and hence more powerful PLAs could be used without undesirably lowering the operating speed of the data processing system.